package com.njupt.Array;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


/**
 * 54. 螺旋矩阵
 */
public class SpiralOrder {

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> integers = new ArrayList<>();
        int startX = 0;
        int starY = 0;
        int offSetX = 1;
        int offSetY = 1;
        int i = 0;
        int j = 0;
        int m = matrix.length;     // 行数
        int n = matrix[0].length;  // 列数
        int loop = 1;

        if (m == 1 && n != 1) {
            for (int k = 0; k < matrix[0].length; k++) {
                integers.add(matrix[0][k]);
            }
            return integers;
        }

        if (n == 1 && m != 1) {
            for (int k = 0; k < matrix.length; k++) {
                integers.add(matrix[k][0]);
            }
            return integers;
        }

        if (n == 1 || m == 1) {
            integers.add(matrix[0][0]);
            return integers;
        }

        while (loop <= m / 2 && loop <= n / 2) {

            //遍历顶部
            for (j = starY; j < n - offSetY; j++) {
                integers.add(matrix[startX][j]);
            }

            //遍历右边
            for (i = startX; i < m - offSetX; i++) {
                integers.add(matrix[i][j]);
            }

            //遍历底部
            for (; j > starY; j--) {
                integers.add(matrix[i][j]);
            }

            //遍历左部
            for (; i > startX; i--) {
                integers.add(matrix[i][j]);
            }
            offSetY++;
            offSetX++;
            loop++;
            startX++;
            starY++;
            if (n - offSetY == 1 && m - offSetX != 1) {
                for (i = startX; i <= m - 2; i++) {
                    integers.add(matrix[i][starY]);
                }
                return integers;
            }
            if (m - offSetX == 1 && n - offSetY != 1) {
                for (j = starY; j <= n - 2; j++) {
                    integers.add(matrix[startX][j]);
                }
                return integers;
            }

            if (m == n && m % 2 != 0) {
                integers.add(matrix[m / 2][n / 2]);
            }


        }

        return integers;
    }

    /**
     * 改进版采用top，left  bottom，right
     *
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> integers = new ArrayList<>();
        int left = 0;
        int top = 0;
        int right = matrix.length - 1;
        int bottom = matrix[0].length - 1;
        if (left == right && top == bottom) {
            integers.add(matrix[0][0]);
        }
        if (left == right && top != bottom) {
            for (int i = 0; i < matrix[0].length; i++) {
                integers.add(matrix[0][i]);
            }
            return integers;
        }
        if (top == bottom && left != right) {
            for (int i = 0; i < matrix.length; i++) {
                integers.add(matrix[i][0]);
            }
            return integers;
        }

        int i = -1;
        int j = -1;
        while (left <= right && top <= bottom) {
            for (j = top; j < bottom; j++) {
                integers.add(matrix[left][j]);
            }

            for (i = left; i < right; i++) {
                integers.add(matrix[i][j]);
            }

            for (; j > top; j--) {
                integers.add(matrix[i][j]);
            }

            for (; i > left; i--) {
                integers.add(matrix[i][j]);
            }
            left++;
            top++;
            right--;
            bottom--;

            if (left == right && top == bottom) {
                integers.add(matrix[left][top]);
                return integers;
            }
        }
        return integers;
    }

    public List<Integer> spiralOrder2(int[][] matrix) {
        List<Integer> integers = new ArrayList<>();


        int rows = matrix.length;
        int columns = matrix[0].length;
        int top = 0, left = 0;
        int bottom = rows - 1;
        int right = columns - 1;
        while (left <= right && top <= bottom) {
            for (int colum = left; colum <= right; colum++) {
                integers.add(matrix[left][colum]);
            }

            for (int row = top + 1; row <= bottom; row++) {
                integers.add(matrix[row][right]);
            }

            if (left < right && top < bottom) {
                for (int colum = right - 1; colum > left; colum--) {
                    integers.add(matrix[bottom][colum]);
                }

                for (int row = bottom; row > top; row--) {
                    integers.add(matrix[row][left]);
                }
            }

            left++;
            top++;
            right--;
            bottom--;
        }
        return integers;
    }

    public static void main(String[] args) {
        int[][] ints = {{2, 3, 4}, {5, 6, 7}, {8, 9, 10}, {11, 12, 13}, {14, 15, 16}};
//        int[][] ints ={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16},{17,18,19,20},{21,22,23,24}};
//        int[][] ints ={{1,2,3},{4,5,6},{7,8,9}};
//        int[][] ints ={{1}};
//        int[][] ints ={{1,2,3}};
//        int[][] ints ={{7},{9},{6}};
        SpiralOrder test = new SpiralOrder();
        List<Integer> list = test.spiralOrder2(ints);
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
    }
}
